import math
from collections import Counter


def euclidean_distance(x1, x2):
    distance = 0.0
    # 逐维度计算差值的平方和
    for a, b in zip(x1, x2):
        distance += (a - b) ** 2
    # 开平方得到欧氏距离
    return math.sqrt(distance)


def knn_classify(X_train, y_train, X_test, k=3):
    # 1. 计算测试样本与所有训练样本的距离
    distances = []
    for i in range(len(X_train)):
        # 计算距离并关联对应标签
        dist = euclidean_distance(X_test, X_train[i])
        distances.append((dist, y_train[i]))  

    # 2. 按距离升序排序
    distances.sort()

    # 3. 选取前k个最近邻的标签
    k_nearest_labels = [item[1] for item in distances[:k]]

    # 4. 投票法：取出现次数最多的标签作为预测结果
    vote_result = Counter(k_nearest_labels)
    # 返回出现次数最多的标签
    return vote_result.most_common(1)[0][0]


# 使用模拟数据测试算法
if __name__ == "__main__":
    # 训练集：特征和对应的标签
    X_train = [
        [1, 2], [1, 4], [1, 0],  # 标签为0的样本
        [4, 2], [4, 4], [4, 0]  # 标签为1的样本
    ]
    y_train = [0, 0, 0, 1, 1, 1]

    # 测试样本
    X_test = [2, 3]  
    k = 3 

    # 预测结果
    prediction = knn_classify(X_train, y_train, X_test, k)
    print(f"测试样本 {X_test} 的预测标签为：{prediction}")